class Solution:
    def countPrefixSuffixPairs(self, words: List[str]) -> int:
        prefixSuffixs = {}
        result = 0
        for word in reversed(words):
            if word in prefixSuffixs:
                result += prefixSuffixs[word]
            next = [-1] * len(word)
            j = -1
            for i in range(1, len(word)):
                while j != -1 and word[j + 1] != word[i]:
                    j = next[j]
                if word[j + 1] == word[i]:
                    j += 1
                next[i] = j

            j = len(word) - 1
            while j != -1:
                prefixSuffixs[word[: j + 1]] = prefixSuffixs.get(word[: j + 1], 0) + 1
                j = next[j]

        return result
